In this paper we show that the Gupta-Belnap systems S# and S* are П12. Since Kremer has independently established that they are П12-hard, this completely settles the problem of their complexity. The above-mentioned upper bound is established through a reduction to countable revision sequences that is inspired by, and makes use of a construction of McGee.

We present an axiomatic approach for a class of finite, extensive form games of perfect information that makes use of notions like “rationality at a node” and “knowledge at a node.” We distinguish between the game theorist's and the players' own “theory of the game.” The latter is a theory that is sufficient for each player to infer a certain sequence of moves, whereas the former is intended as a justification of such a sequence of moves. While in general the (...) game theorist's theory of the game is not and need not be axiomatized, the players' theory must be an axiomatic one, since we model players as analogous to automatic theorem provers that play the game by inferring (or computing) a sequence of moves. We provide the players with an axiomatic theory sufficient to infer a solution for the game (in our case, the backwards induction equilibrium), and prove its consistency. We then inquire what happens when the theory of the game is augmented with information that a move outside the inferred solution has occurred. We show that a theory that is sufficient for the players to infer a solution and still remains consistent in the face of deviations must be modular. By this we mean that players have distributed knowledge of it. Finally, we show that whenever the theory of the game is group-knowledge (or common knowledge) among the players (i.e., it is the same at each node), a deviation from the solution gives rise to inconsistencies and therefore forces a revision of the theory at later nodes. On the contrary, whenever a theory of the game is modular, a deviation from equilibrium play does not induce a revision of the theory. (shrink)

In this paper we apply the idea of Revision Rules, originally developed within the framework of the theory of truth and later extended to a general mode of definition, to the analysis of the arithmetical hierarchy. This is also intended as an example of how ideas and tools from philosophical logic can provide a different perspective on mathematically more “respectable” entities. Revision Rules were first introduced by A. Gupta and N. Belnap as tools in the theory of truth, and they (...) have been further developed to provide the foundations for a general theory of (possibly circular) definitions. Revision Rules are non-monotonic inductive operators that are iterated into the transfinite beginning with some given “bootstrapper” or “initial guess.” Since their iteration need not give rise to an increasing sequence, Revision Rules require a particular kind of operation of “passage to the limit,” which is a variation on the idea of the inferior limit of a sequence. We then define a sequence of sets of strictly increasing arithmetical complexity, and provide a representation of these sets by means of an operator G(x, φ) whose “revision” is carried out over ω2 beginning with any total function satisfying certain relatively simple conditions. Even this relatively simple constraint is later lifted, in a theorem whose proof is due to Anil Gupta. (shrink)

In this paper we argue that Revision Rules, introduced by Anil Gupta and Nuel Belnap as a tool for the analysis of the concept of truth, also provide a useful tool for defining computable functions. This also makes good on Gupta's and Belnap's claim that Revision Rules provide a general theory of definition, a claim for which they supply only the example of truth. In particular we show how Revision Rules arise naturally from relaxing and generalizing a classical construction due (...) to Kleene, and indicate how they can be employed to reconstruct the class of the general recursive functions. We also point at how Revision Rules can be employed to access non-minimal fixed points of partially defined computing procedures. (shrink)

Gian Aldo Antonelli and Cristina Bicchieri. Backwards Forwards Induction.

Gian Aldo Antonelli and Cristina Bicchieri. Forward Induction.

Quine’s “New Foundations” (NF) was first presented in Quine [1937] and later on in Quine [1963]. Ernst Specker [1958, 1962], building upon a previous result of Ehrenfeucht and Mostowski [1956], showed that NF is consistent if and only if there is a model of the Theory of Negative (and positive) Types (TNT) with full extensionality that admits of a “shifting automorphism,” but the existence of a such a model remains an open problem.